/**
 * 
 */
package recursion;

import utils.CreateUtils;
import utils.PrintUtils;

import java.util.ArrayList;

/**
 * @author Michael
 * Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
 *
 * For example,
 * Given the following matrix:
 * [
 *  [ 1, 2, 3 ],
 *  [ 4, 5, 6 ],
 *  [ 7, 8, 9 ]
 * ]
 * You should return [1,2,3,6,9,8,7,4,5].
 */
public class PrintMatrixInSpiralOrder {

	// seems correct but cannot pass LOJ
	
	public static void printSpiralRecursive(int[][] m, int numRows, int numCols, int k) {
		if (numRows <= 0 || numCols <= 0)
			return;
		
		if (numRows == 1) {
			for (int row = k, col = k, toCol = k + numCols; col < toCol; ++col) {
				System.out.printf("%d ", m[row][col]);
			}
			return;
		}
		if (numCols == 1) {
			for (int row = k, col = k, toRow = numRows + k; row < toRow; ++row) {
				System.out.printf("%d ", m[row][col]);
			}
			return;
		}
		
		//print top
		for (int row = k, col = k, toCol = numCols + k - 1; col < toCol; ++col) {
			System.out.printf("%d ", m[row][col]);
		}
		
		// print left
		for (int row = k, col = k + numCols - 1, toRow = k + numRows - 1; row < toRow; ++row) {
			System.out.printf("%d ", m[row][col]);
		}
		
		//print bottom
		for (int row = k + numRows - 1, col = k + numCols - 1, fromCol = k; col > fromCol; --col) {
			System.out.printf("%d ", m[row][col]);
		}
		
		//right right
		for (int row = k + numRows - 1, col = k, fromRow = k; row > fromRow; --row) {
			System.out.printf("%d ", m[row][col]);
		}
		
		printSpiralRecursive(m, numRows - 2, numCols - 2, k + 1);
	}
	
	public static ArrayList<Integer> printSpiralIterative(int[][] m) {
		assert (m != null);
		if (m.length == 0)
			assert (false);
		if (m[0].length == 0)
			assert (false);

		int level = 0;
		int rows = m.length;
		int cols = m[0].length;
		int rowsLeft;
		int colsLeft;
		ArrayList<Integer> arrList = new ArrayList<Integer>(rows * cols);
		
		while ( (rowsLeft = (rows - level * 2)) > 0 && (colsLeft = cols - level * 2) > 0) {
			// print top
			for (int col = level, row = level,  to = cols - level; col < to; ++col) {
				System.out.printf("%d ", m[row][col]);
				arrList.add(m[row][col]);
			}
			
			// print left
			for (int row = level + 1, col = cols - level - 1, to = rows - level; row < to; ++row) {
				System.out.printf("%d ", m[row][col]);
				arrList.add(m[row][col]);
			}
			
			// print bottom
			if (rowsLeft >= 2 && colsLeft >= 2)
				for (int col = cols - level - 2, row = rows - level - 1; col >= level; --col) {
					System.out.printf("%d ", m[row][col]);
					arrList.add(m[row][col]);
				}
			
			// print right
			if (rowsLeft >= 2 && colsLeft >= 2)
				for (int row = rows - level - 2, col = level; row > level; --row) {
					System.out.printf("%d ", m[row][col]);
					arrList.add(m[row][col]);
				}
			
			++level;
		}
		
		return arrList;
	}
	
	/**
	 * 
	 */
	public PrintMatrixInSpiralOrder() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] m = { { 1, 2, 3, 4 }, 
				      { 5, 6, 7, 8 }, 
				      { 9, 10, 11, 12 } };
		printSpiralIterative(m);
		System.out.println();
		printSpiralRecursive(m, m.length, m[0].length, 0);
		System.out.printf("\n\n");

		m = new int[][] { { 1, 2, 3 }, 
				          { 4, 5, 6 }, 
				          { 7, 8, 9 }, 
				          { 10, 11, 12 } };
		printSpiralIterative(m);
		System.out.println();
		printSpiralRecursive(m, m.length, m[0].length, 0);
		System.out.printf("\n\n");

		m = new int[][] { { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } };
		printSpiralIterative(m);
		System.out.println();
		printSpiralRecursive(m, m.length, m[0].length, 0);
		System.out.printf("\n\n");

		m = new int[][] { { 1 }, { 2 }, { 3 }, { 4 }, { 5 }, { 6 }, { 7 },
				{ 8 }, { 9 }, { 10 }, { 11 }, { 12 } };
		printSpiralIterative(m);
		System.out.println();
		printSpiralRecursive(m, m.length, m[0].length, 0);
		System.out.printf("\n\n");

		m = new int[][] { { 1, 2, 3 }, 
				          { 4, 5, 6 }, 
				          { 7, 8, 9 } };
		printSpiralIterative(m);
		System.out.println();
		printSpiralRecursive(m, m.length, m[0].length, 0);
		System.out.printf("\n\n");

		m = CreateUtils.randNonNegMatrix(10, 20, false);
		PrintUtils.print2DArray(m);
		printSpiralIterative(m);
		System.out.println();
		printSpiralRecursive(m, m.length, m[0].length, 0);
		System.out.printf("\n\n");

	}

}
